package Top_Interview_Questions.Dynamic_Programming;

import java.util.Arrays;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/6 12:22
 * <p>
 * https://leetcode-cn.com/problems/coin-change/solution/dong-tai-gui-hua-tao-lu-xiang-jie-by-wei-lai-bu-ke/
 * 这个题解又是一篇动态规划套路的解答
 */
public class _0322 {

    public static void main(String[] args) {
        _0322 test = new _0322();
        int[] coins = {1,2,5};
        test.coinChange(coins, 11);
    }

    /**
     * dp[i] = x 表示，当目标金额为 i 时，至少需要 x 枚硬币
     */
    public int coinChange(int[] coins, int amount) {
        // 数组大小为 amount + 1，初始值也为 amount + 1

        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        // base case
        dp[0] = 0;
        for (int i = 0; i < dp.length; i++) {
            // 内层 for 在求所有子问题 + 1 的最小值
            for (int coin : coins) {
                // 子问题无解，跳过
                if (i - coin < 0)
                    continue;
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];

    }
}
